第8.2节 决策树的生成之ID3与C4.5
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
8.2 决策树的生成之ID3与C4.5 8.2.1 基本概念与定义 8.2.2 计算示例 8.2.3 ID3生成算法 8.2.4 C4.5生成算法 8.2.5 特征划分 8.2.6 小结 引用
8.2 决策树的生成之ID3与C4.5
在正式介绍决策树的生成算法前，笔者先将第8.1.1节中介绍的几个概念重新梳理一下，同时再通过一个例子来熟悉一下计算过程，以便于后续更好地理解决策树的生成算法。
8.2.1 基本概念与定义
1. 信息熵
设是一个取值有限的离散型随机变量（例如第8.1.1节中可能夺冠的16支球队），其概率分布为（每支球队可能夺冠的概率），则随机变量的信息熵定义为
其中，若，则定义，并且通常取为底或为底时，其熵的单位分别称为比特（Bit）或纳特（Nat）。如无特殊说明，默认以为底。
2. 条件熵
设有随机变量，其联合概率分布分，其中，条件熵表示在已知随机变量的条件下，随机变量的不确定性，其定义为
其中，。
同时，当信息熵和条件熵中的概率由样本数据估计（特别是极大似然估计）得到时，所对应的信息熵与条件熵分别称为经验熵（Empirical Entropy）和经验条件熵（Empirical Conditional Entropy）。这里暂时看不懂也没关系，可结合后续计算示例来理解。
3. 信息增益
从8.1.1节的内容可知，所谓信息增益指的就是事物U的信息熵，在引入外部信息I后的变化量为，因此，可以将特征对训练数据集的信息增益定义为集合的信息熵与特征给定条件下的条件熵之差，即
定义： 设训练集为，表示所有训练样本总数，同时有个类别。为属于类的样本总数，即 。设特征有个不同的取值，根据特征的取值将划分为个子集，为子集中的样本个数，即。同时此子集中，属于类的样本集合为，即，为的样本个数。此时有如下定义[1]。
(1) 数据集的经验熵为
从式(8.8)可以看出，它计算的是“任意样本属于其中一个类别”这句话所包含的信息量。
(2) 数据集在特征值下的经验条件熵为
从式(8.9)可以看出，它计算的是特征在各个取值条件下“任意样本属于其中一个类别”这句话所包含的信息量。
(3) 信息增益为
8.2.2 计算示例
如果仅看上面的公式肯定不那么容易理解，下面笔者再进行举例说明（将上面的公式同下面的计算过程对比看会更容易理解)。表8-1同样是6.1.3节中用过的一个信用卡审批数据集，其一共包含15个样本和3个特征维度。其中特征表示有无工作，特征表示是否有房，特征表示学历等级，表示是否审批通过的类标记。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！
1. 计算信息熵
根据式(8.8)可得